//删除链表的倒数第 N 个结点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* _head = new ListNode(-1, head);
        ListNode* prev = _head;
        ListNode* cur = head;
        ListNode* fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
        while (fast) {
            prev = cur;
            cur = cur->next;
            fast = fast->next;
        }
        prev->next = cur->next;

        return _head->next;
    }
};


//随机链表的复制
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> hash;
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
            return nullptr;
        Node* cur = new Node(head->val);
        hash[head] = cur;
        cur->next = copyRandomList(head->next);
        cur->random = hash[head->random];
        return cur;
    }
};